# -*- coding: utf-8 -*-
# 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效

# 有效字符串需满足：
# 左括号必须用相同类型的右括号闭合
# 左括号必须以正确的顺序闭合
# 注意空字符串可被认为是有效字符串

# 示例 1:

# 输入: "()"
# 输出: true
# 示例 2:

# 输入: "()[]{}"
# 输出: true
# 示例 3:

# 输入: "(]"
# 输出: false
# 示例 4:

# 输入: "([)]"
# 输出: false
# 示例 5:

# 输入: "{[]}"
# 输出: true

# # 一遍过，很简单嘛
# class Solution(object):
#     def isValid(self, s):
#         """
#         :type s: str
#         :rtype: bool
#         """
#         valid_pairs = ["()","[]","{}"];
#         in_stack = [];
#         for i in xrange(0, len(s)):
#             for j in xrange(0, len(valid_pairs)):
#                 if s[i] == valid_pairs[j][0]:
#                     in_stack.append(s[i]);
#                     break;
#                 elif s[i] == valid_pairs[j][1]:
#                     if len(in_stack) == 0:
#                         return False;
#                     last = in_stack.pop(len(in_stack) - 1);
#                     if last != valid_pairs[j][0]:
#                         return False;
#         return len(in_stack) == 0;









# 查看官方解答，写法更简单行数更少
# 学习到的内容
# 1、?:的python写法last = in_stack.pop() if in_stack else "#"
# 2、非空即是真
# 3、hash_map的应用总是不能及时的想到
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        valid_pairs = {")":"(", "]":"[", "}":"{"};
        in_stack = [];
        for char_s in s:
            if char_s in valid_pairs:
                last = in_stack.pop() if in_stack else "#";
                if last != valid_pairs[char_s]:
                    return False;
            else:
                in_stack.append(char_s);
        return not in_stack;
t = Solution();
print t.isValid("()")